package Algorithm.sort;

/**
 * @Desc:   归并排序
 * https://www.cnblogs.com/chengxiao/p/6194356.html
 * @author: cww
 * @DateTime: 2020/4/13 19:00
 */

public class MergeSort {
    public static void main(String[] args) {
        int[] i = new int[]{8,4,5,7,1,3,6,2};
        sort(i);
        System.out.println();
    }

    public static void sort(int[] array){
        int len = array.length;
        int[] temp = new int[len];
        sort(array,0,len-1,temp);
    }

    public static void sort(int[] arr, int left, int right, int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);
            sort(arr,mid + 1,right,temp);
            merge(arr,left,mid,right,temp);
        }

    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = left;
        int j = mid + 1;
        int t =0;
        while (i<=mid&&j<=right){
            if (arr[i]<arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while (i<=mid) temp[t++] = arr[i++];
        while (j<=right) temp[t++] = arr[j++];
        t=0;
        while (left<=right) arr[left++] = temp[t++];
    }
}
